package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

/**
 * @author zhangjy
 * @description 二叉搜索树中的插入操作
 * @date 2025/4/26 17:03
 */
public class InsertIntoBST_701 {

    /**
     * dmsxl解法
     */
    public TreeNode insertIntoBST3(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);

        if (root.val > val) {
            root.left = insertIntoBST3(root.left, val);
        }
        if (root.val < val) {
            root.right = insertIntoBST3(root.right, val);
        }

        return root;
    }

    /**
     * dfs-迭代
     */
    public TreeNode insertIntoBST2(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);

        TreeNode node = root;
        while (node != null) {
            if (node.val > val) {
                if (node.left == null) {
                    TreeNode cur = new TreeNode(val);
                    node.left = cur;
                    break;
                } else {
                    node = node.left;
                }

            } else {
                if (node.right == null) {
                    TreeNode cur = new TreeNode(val);
                    node.right = cur;
                    break;
                } else {
                    node = node.right;
                }
            }
        }
        return root;
    }

    /**
     * 个解：dfs-递归
     * <p>
     * 分析：
     * 1.先找到插入位置；
     * 2.再插入，此时要知道父节点。
     * <p>
     * 思路：BST，中序遍历节点值严格有序，同时，树结构也是按节点值构建。
     * 所以，根据val和当前节点的大小，判断往node左 还是 右 孩子向下遍历，当遍历到叶子节点，就找到了插入位置。
     */
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);

        TreeNode node = root;
        dfs(node, val);
        return root;
    }

    TreeNode pre = null;

    public void dfs(TreeNode node, int val) {
        if (node == null) {
            TreeNode cur = new TreeNode(val);
            if (pre.left == null && pre.val > val) {
                pre.left = cur;
            } else {
                pre.right = cur;
            }
            return;
        }

        pre = node;
        // 左
        if (node.val > val) dfs(node.left, val);
        // 右
        if (node.val < val) dfs(node.right, val);

    }

}
